package main

import (
	"fmt"
)

/**
执行用时：12 ms, 在所有 Go 提交中击败了53.31%的用户
内存消耗：6.3 MB, 在所有 Go 提交中击败了83.91%的用户
 */
var ans [][]int
var path []int
var k int

func combine(n int, _k int) [][]int {

	k = _k
	ans = [][]int{}
	path = make([]int, k)
	dfs(n, 0, 1)
	return ans
}

func dfs(n int, u int, start int) {

	if u == k {
		t := make([]int, len(path))
		copy(t, path)
		ans = append(ans, t)
		return
	}

	for i := start; i <= n; i++ {
		path[u] = i
		dfs(n, u + 1, i + 1)
	}
}

func main() {

	fmt.Println(combine(4, 2))
}
